import math
import random 
from typing import List

def radix_counting_sort(A, values, bin_values):
    """ A对应截取二进制段的对应值，values对应原数值，bin_values对应原数值的二进制形式 """
    k = 0
    for element in A:
        if isinstance(element, int) is False or element < 0:
            raise Exception("Element has to be integer and no minus.")
        if element > k:
            k = element
    buffer_array = []
    for i in range(0, k + 1):
        buffer_array.append(0)
    for element in A:
        buffer_array[element] += 1
    for i in range(1, len(buffer_array)):
        buffer_array[i] = buffer_array[i - 1] + buffer_array[i]
    sorted_array = []
    sorted_array_values = []
    sorted_array_bin_values = []

    for i in range(0, len(A)):
        sorted_array.append(0)
        sorted_array_values.append(0)
        sorted_array_bin_values.append(0)
    A = A[::-1]
    values = values[::-1]
    bin_values = bin_values[::-1]
    for element, value, bin_value in zip(A, values, bin_values):
        position = buffer_array[element]
        sorted_array[position - 1] = element
        sorted_array_values[position - 1] = value
        sorted_array_bin_values[position - 1] = bin_value
        buffer_array[element] -= 1
    return sorted_array, sorted_array_values, sorted_array_bin_values


def radix_sorted(A:List[int]):
    b = 0
    for element in A:
        if element.bit_length() > b:
            b = element.bit_length()
    """ 将元素转换为二进制字符串，例如 A = [10, 9, 2, 1]，元素对应二进制[0b1010, 0b1001, 0b10, 0b01].
    由于数值元素中比特位个数最多为4，因此需要将所有元素对应的二进制比特位扩展成4，也就是将元素的二进制形式转换为
    [0b1010, 0b1001, 0b0010, 0b0001]."""
    bin_A = []      # type(bin_A[0]) = str
    for element in A:
        bin_element = ''        # type(element) = int
        le = b - element.bit_length()
        while le > 0:
            bin_element += '0'
            le -= 1
        bin_element += bin(element)[2:]
        bin_A.append(bin_element)
            
    n = len(A)
    r = int(math.log(n, 2))
    if b <= math.log(n, 2):
        r = b
    count = math.ceil(b / r)
    end = b
    begin = 0
    while count > 0:
        values_for_sort = []
        begin = 0 if end - r < 0 else end - r

        for element in bin_A:
            if end > len(element):
                end = element.bit_length()
                print(f"the var end's type is {type(end)}")
                print(f"the var end is {end}")
            print(f"The 'begin': {begin}, and the 'end': {end}")
            v = int(element[begin : end])
            print(f"Get the radix str: {v}.")

            values_for_sort.append(v)
        V, A, bin_A = radix_counting_sort(values_for_sort, A, bin_A)
        count -= 1
        end -= r
    return A


# A = [10, 9, 2, 1]
# A = radix_sorted(A)
# print(A)

if __name__ == "__main__":
    ## 生成数据验证算法正确性
    N = 20
    A = []
    for i in range(N):
        A.append(random.randint(1, 1000))
    print(f"Before radix sort : {A}")
    A = radix_sorted(A)
    print(f"After radix sort : {A}")

